#include <vector>
#include <string>
#include <stack>

using namespace std;

// 2582. 递枕头
class Solution1
{
public:
    int passThePillow(int n, int time) 
    {
        int m = time / (n - 1);
        int step = time % (n - 1);
        return m % 2 == 0 ? 1 + step : n - step;    
    }
};

// 316. 去除重复字母
class Solution 
{
public:
    string removeDuplicateLetters(string s) 
    {
        int cnt[26]{};
        for(char ch : s) ++cnt[ch - 'a'];

        string ret;
        bool visited[26]{};
        for(char ch : s)
        {
            --cnt[ch - 'a'];
            if(visited[ch - 'a']) continue;
            while(!ret.empty() && ch < ret.back() && cnt[ret.back() - 'a'])
            {
                visited[ret.back() - 'a'] = false;
                ret.pop_back();
            }
            ret += ch;
            visited[ch - 'a'] = true;
        }

        return ret;
    }
};

// 2289. 使数组按非递减顺序排列
class Solution3
{
public:
    int totalSteps(vector<int>& nums) 
    {
        int ret = 0;
        stack<pair<int, int>> st;
        for(int x : nums)
        {
            int maxT = 0;
            while(!st.empty() && st.top().first <= x)
            {
                maxT = max(maxT, st.top().second);
                st.pop();
            }
            maxT = st.empty() ? 0 : maxT + 1;
            ret = max(ret, maxT);
            st.emplace(x, maxT);
        }    

        return ret;
    }
};

// 1827. 最少操作使数组递增
class Solution4
{
public:
    int minOperations(vector<int>& nums) 
    {
        int ret = 0, n = nums.size();
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] <= nums[i - 1])
            {
                int diff = nums[i - 1] - nums[i] + 1;
                nums[i] += diff;
                ret += diff;
            }
        }
        return ret;
    }
};

// 907. 子数组的最小值之和
class Solution5
{
public:
    int sumSubarrayMins(vector<int>& arr) 
    {
        int n = arr.size();
        vector<int> st;
        vector<int> left(n), right(n);
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && arr[i] <= arr[st.back()]) st.pop_back();
            left[i] = i - (st.empty() ? -1 : st.back());
            st.push_back(i);
        }

        st.clear();
        for(int i = n - 1; i >= 0; --i)
        {
            while(!st.empty() && arr[i] < arr[st.back()]) st.pop_back();
            right[i] = (st.empty() ? n : st.back()) - i;
            st.push_back(i);
        }

        long long ret = 0;
        const long long MOD = 1e9 + 7;
        for(int i = 0; i < n; ++i)
        {
            ret = (ret + (long long)left[i] * right[i] * arr[i]) % MOD;
        }
        return ret;
    }
};

// 402. 移掉 K 位数字
class Solution6
{
public:
    string removeKdigits(string num, int k) 
    {
        vector<char> st;
        for(char digit : num)
        {
            while(!st.empty() && st.back() > digit && k)
            {
                st.pop_back();
                --k;
            }
            st.push_back(digit);
        }

        for(; k > 0; --k) st.pop_back();

        string ret;
        bool isLeadingZero = true;
        for(char digit : st)
        {
            if(isLeadingZero && digit == '0') continue;
            isLeadingZero = false;
            ret += digit;
        }
        return ret.empty() ? "0" : ret;
    }
};

// 2285. 道路的最大总重要性
class Solution7
{
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) 
    {
        vector<int> deg(n);
        for(auto& e : roads)
        {
            ++deg[e[0]];
            ++deg[e[1]];
        }

        sort(deg.begin(), deg.end());
        long long ret = 0;
        for(int i = 0; i < n; ++i)
        {
            ret += (long long)deg[i] * (i + 1);
        }
        return ret;
    }
};

// 2286. 以组为单位订音乐会的门票
class BookMyShow 
{
    int n, m;
    vector<int> min;
    vector<long> sum;

    // 将 idx 上的元素值增加 val
    // 调用方式：add(1, 1, n, idx, val)，1 是根节点的编号
    // [l, r] 是节点 o 所管理的区间
    void add(int o, int l, int r, int idx, int val) 
    {
        if (l == r) 
        {
            min[o] += val;
            sum[o] += val;
            return;
        }
        int m = (l + r) / 2;
        if (idx <= m) add(o * 2, l, m, idx, val);
        else add(o * 2 + 1, m + 1, r, idx, val);
        min[o] = std::min(min[o * 2], min[o * 2 + 1]);
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
    }

    // 返回区间 [L,R] 内的元素和
    // 调用方式：query_sum(1, 1, n, L, R)，1 是根节点的编号
    long query_sum(int o, int l, int r, int L, int R) 
    { 
        // L 和 R 在整个递归过程中均不变，将其大写，视作常量
        if (L <= l && r <= R) return sum[o];
        long sum = 0L;
        int m = (l + r) / 2;
        if (L <= m) sum += query_sum(o * 2, l, m, L, R);
        if (R > m) sum += query_sum(o * 2 + 1, m + 1, r, L, R);
        return sum;
    }

    // 返回区间 [1,R] 中 <= val 的最靠左的位置，不存在时返回 0
    int index(int o, int l, int r, int R, int val) 
    { 
        // R 在整个递归过程中均不变，将其大写，视作常量
        if (min[o] > val) return 0; // 说明整个区间的元素值都大于 val
        if (l == r) return l;
        int m = (l + r) / 2;
        if (min[o * 2] <= val) return index(o * 2, l, m, R, val); // 看看左半部分
        if (m < R) return index(o * 2 + 1, m + 1, r, R, val); // 看看右半部分
        return 0;
    }

public:
    BookMyShow(int n, int m) : n(n), m(m), min(n * 4), sum(n * 4) {}

    vector<int> gather(int k, int maxRow) 
    {
        int i = index(1, 1, n, maxRow + 1, m - k);
        if (i == 0) return {}; // 不存在
        int seats = query_sum(1, 1, n, i, i);
        add(1, 1, n, i, k); // 占据 k 个座位
        return {i - 1, seats};
    }

    bool scatter(int k, int maxRow) 
    {
        if ((long) (maxRow + 1) * m - query_sum(1, 1, n, 1, maxRow + 1) < k) return false; // 剩余座位不足 k 个
        // 从第一个没有坐满的排开始占座
        for (int i = index(1, 1, n, maxRow + 1, m - 1);; ++i) 
        {
            int left_seats = m - query_sum(1, 1, n, i, i);
            if (k <= left_seats) 
            { 
                // 剩余人数不够坐后面的排
                add(1, 1, n, i, k);
                return true;
            }
            k -= left_seats;
            add(1, 1, n, i, left_seats);
        }
    }
};

// 2569. 更新数组后处理求和查询
class Solution8
{
    static constexpr int MX = 4e5 + 1;
    int cnt1[MX];
    bool flip[MX];

    // 维护区间 1 的个数
    void maintain(int o)
    {
        cnt1[o] = cnt1[o * 2] + cnt1[o * 2 + 1]; 
    }

    // 执行区间反转
    void do_(int o, int l, int r)
    {
        cnt1[o] = r - l + 1 - cnt1[o];
        flip[o] = !flip[o];
    }

    // 初始化线段树
    void build(vector<int>& a, int o, int l, int r)
    {
        if(l == r)
        {
            cnt1[o] = a[l - 1];
            return;
        }

        int m = (r + l) / 2;
        build(a, 2 * o, l, m);
        build(a, 2 * o + 1, m + 1, r);
        maintain(o);
    }

    // 反转区间 [L, R]
    void update(int o, int l, int r, int L, int R)
    {
        if(L <= l && r <= R)
        {
            do_(o, l, r);
            return;
        }

        int m = (r + l) / 2;
        if(flip[o])
        {
            do_(2 * o, l, m);
            do_(2 * o + 1, m + 1, r);
            flip[o] = false;
        }
        if(m >= L) update(2 * o, l, m, L, R);
        if(m < R) update(2 * o +1, m + 1, r, L, R);
        maintain(o);
    }

public:
    vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) 
    {
        int n = nums1.size();
        build(nums1, 1, 1, n);
        vector<long long> ret;
        long long sum = accumulate(nums2.begin(), nums2.end(), 0LL);
        for(auto& q : queries)
        {
            if(q[0] == 1) update(1, 1, n, q[1] + 1, q[2] + 1);
            else if(q[0] == 2) sum += 1LL * q[1] * cnt1[1];
            else ret.push_back(sum);
        }
        return ret;
    }
};